//给你一个正方形字符数组 board ，你从数组最右下方的字符 'S' 出发。 
//
// 你的目标是到达数组最左上角的字符 'E' ，数组剩余的部分为数字字符 1, 2, ..., 9 或者障碍 'X'。在每一步移动中，你可以向上、向左或者左上
//方移动，可以移动的前提是到达的格子没有障碍。 
//
// 一条路径的 「得分」 定义为：路径上所有数字的和。 
//
// 请你返回一个列表，包含两个整数：第一个整数是 「得分」 的最大值，第二个整数是得到最大得分的方案数，请把结果对 10^9 + 7 取余。 
//
// 如果没有任何路径可以到达终点，请返回 [0, 0] 。 
//
// 
//
// 示例 1： 
//
// 
//输入：board = ["E23","2X2","12S"]
//输出：[7,1]
// 
//
// 示例 2： 
//
// 
//输入：board = ["E12","1X1","21S"]
//输出：[4,2]
// 
//
// 示例 3： 
//
// 
//输入：board = ["E11","XXX","11S"]
//输出：[0,0]
// 
//
// 
//
// 提示： 
//
// 
// 2 <= board.length == board[i].length <= 100 
// 
//
// Related Topics 数组 动态规划 矩阵 👍 82 👎 0


package com.tyrone.leetcode.editor.cn;

import java.util.List;

public class NumberOfPathsWithMaxScore {
    public static void main(String[] args) {
        Solution solution = new NumberOfPathsWithMaxScore().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        int cache[][];
        int[][] dir = {{1, 0}, {0, 1}, {1, 1}};
        int n;
        int mod = (int) 1e9 + 7;

        /**
         * 这道题包含了两个问题 最大分数 和 最多方案数
         *
         * @param board
         * @return
         */
        public int[] pathsWithMaxScore(List<String> board) {
            n = board.size();
            char[][] cs = new char[n][n];
            for (int i = 0; i < n; i++) {
                cs[i] = board.get(i).toCharArray();
            }
            int[] f = new int[n * n]; //f[i]表示右下角到i的最大分数
            int[] g = new int[n * n]; //g[i]表示右下角到i的最大分数时的最大方案数

            for (int i = n - 1; i >= 0; i--) {
                for (int j = n - 1; j >= 0; j--) {
                    int idx = getIdx(i, j);
                    //如果起点
                    if (i == n - 1 & j == n - 1) {
                        g[idx] = 1;
                        continue;

                    }
                    //如果是障碍
                    if (cs[i][j] == 'X') {
                        f[idx] = Integer.MIN_VALUE;
                        continue;
                    }

                    int val = (i == 0 && j == 0) ? 0 : cs[i][j] - '0';
                    // u 代表当前位置的「最大得分」；t 代表取得最大得分的「方案数」
                    int u = Integer.MIN_VALUE, t = 0;

                    if (i + 1 < n) {
                        int cur = f[getIdx(i + 1, j)] + val;
                        int cnt = g[getIdx(i + 1, j)];
                        int[] res = update(cur, cnt, u, t);
                        u = res[0];
                        t = res[1];
                    }
                    if (j + 1 < n) {
                        int cur = f[getIdx(i, j + 1)] + val;
                        int cnt = g[getIdx(i, j + 1)];
                        int[] res = update(cur, cnt, u, t);
                        u = res[0];
                        t = res[1];
                    }
                    if (i + 1 < n && j + 1 < n) {
                        int cur = f[getIdx(i + 1, j + 1)] + val;
                        int cnt = g[getIdx(i + 1, j + 1)];
                        int[] res = update(cur, cnt, u, t);
                        u = res[0];
                        t = res[1];
                    }
                    f[idx] = u < 0 ? Integer.MIN_VALUE : u;
                    g[idx] = t;

                }
            }
            int[] ans = new int[2];
            ans[0] = f[getIdx(0, 0)] == Integer.MIN_VALUE?0:f[getIdx(0, 0)];
            ans[1] = f[getIdx(0, 0)] == Integer.MIN_VALUE?0:g[getIdx(0,0)];
            return ans;

        }


        int[] update(int cur, int cnt, int u, int t) {
            // 起始答案为 [u, t] : u 为「最大得分」，t 为最大得分的「方案数」
            int[] ans = new int[]{u, t};

            // 如果当前值大于 u，更新「最大得分」和「方案数」
            if (cur > u) {
                ans[0] = cur;
                ans[1] = cnt;

                // 如果当前值等于 u，增加「方案数」
            } else if (cur == u && cur != Integer.MIN_VALUE) {
                ans[1] += cnt;
            }

            ans[1] %= mod;
            return ans;
        }

        // 二维坐标 (x,y) 与 idx 的相互转换
        int getIdx(int x, int y) {
            return x * n + y;
        }

        int[] parseIdx(int idx) {
            return new int[]{idx / n, idx % n};
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}